package 我的Java学习_算法基础.day_04;

import java.util.Arrays;

import static 我的Java学习_算法基础.day_04._066_编程返回子数组最大累加和.findByDP;

public class _067_求子距阵最大累加和 {
    public static void main(String[] args) {
        int[][] a ={
                {-1,    -1, -1},
                {-1,    2,  2},
                {-1,    -1, -1}};
        int max = maxSum(a);
        System.out.println(max);
    }
    private static int maxSum(int[][] array){
        int beginRow = 0;//起始行
        final int m = array.length;
        final int n = array[0].length;
        int[] sums = new int[n];    //按列求和
        int max = 0;    //历史最大子矩阵和

        while(beginRow<m){
            for(int i = beginRow;i<m;i++){
                //按列累加
                for(int j = 0;j<n;j++){
                    sums[j]+=array[i][j];
                }
                int t =findByDP(sums);//到当前行及以上相邻列最大累加和
                if(t>max){
                    max = t;
                }
            }
            Arrays.fill(sums,0);//sums清零
            beginRow++; //从下一行开始
        }
        return max;
    }
}
